package com.mango.leet.code.week1.game289;

import java.math.BigInteger;
import java.util.*;

/**
 * 6072. 转角路径的乘积中最多能有几个尾随零
 * @Author: mango
 * @Date: 2022/4/17 11:44 上午
 */
public class LC6072 {
    public static void main(String[] args) {
        //int[][] grid = {{23,17,15,3,20},{8,1,20,27,11},{9,4,6,2,21},{40,9,1,10,6},{22,7,4,5,3}};
        //int[][] grid = {{899,727,165,249,531,300,542,890},{981,587,565,943,875,498,582,672},{106,902,524,725,699,778,365,220}};
        //int[][] grid = {{10},{6},{15}};
        //int[][] grid = {{596},{991},{748},{1000},{904},{922},{940},{962}};
        int[][] grid = {{959},{353},{667},{672},{713},{595},{110}};
        System.out.println(new Solution().maxTrailingZeros(grid));

    }
    static class Solution {
        public int maxTrailingZeros(int[][] grid) {
            // 先找元素种子 5,10,15,20,25
            Set<Node> seedSet = new LinkedHashSet<>();
            for(int i=0;i<grid.length;i++){
                for(int j=0;j<grid[i].length;j++){
                    if(grid[i][j] % 5 == 0){
                        seedSet.add(new Node(i,j,grid[i][j]));
                    }
                }
            }
            // 如果seedCount = 0,则直接返回0
            if(seedSet.size() == 0){
                return 0;
            }
            int result = 0;
            // 种子节点连线，不在同一列中的点
            for(Node node1 : seedSet){
                for(Node node2 : seedSet){
                    if(node1.x == node2.x && node1.y == node2.y){
                        continue;
                    }
                    /*if(node1.x == node2.x){
                        // 跳过，在同一行，无法形成直角
                        continue;
                    }
                    if(node1.y == node2.y){
                        // 跳过，在同一列，无法形成直角
                        continue;
                    }*/
                    int theResult = process(grid,node1,node2);
                    result = Math.max(theResult,result);
                }
            }

            return result;
        }

        private int process(int[][] grid,Node node1, Node node2) {
            // 1. 先横向移动
            BigInteger sum = new BigInteger("1");

            if(node1.y > node2.y){
                // 交换
                Node temp = node1;
                node1 = node2;
                node2 = temp;
            }
            if(node1.y != node2.y) {
                System.out.println("横向:");
                System.out.println("node1=" + node1.toString());
                System.out.println("node2=" + node2.toString());
                // node1 在 node2左边
                for (int i = node1.y; i <= node2.y; i++) {
                    sum = sum.multiply(new BigInteger(grid[node1.x][i] + ""));
                    System.out.println("x*" + grid[node1.x][i]);
                }
                int x1 = Math.min(node1.x, node2.x);
                int x2 = Math.max(node1.x, node2.x);
                for (int j = x1; j < x2; j++) {
                    sum = sum.multiply(new BigInteger(grid[j][node2.y] + ""));
                    System.out.println("y*" + grid[j][node2.y]);
                }
            }

            System.out.println("sum1="+sum);
            BigInteger sum2 = new BigInteger("1");
            // 2. 先纵向移动
            if(node1.x != node2.x) {
                System.out.println("纵向:");
                System.out.println("node1=" + node1.toString());
                System.out.println("node2=" + node2.toString());
                // node1 在 node2左边
                int x21 = Math.min(node1.x, node2.x);
                int x22 = Math.max(node1.x, node2.x);
                for (int j = x21; j <= x22; j++) {
                    sum2 = sum2.multiply(new BigInteger(grid[j][node1.y] + ""));
                    System.out.println("y*" + grid[j][node1.y]);

                }
                for (int i = node1.y + 1; i <= node2.y; i++) {
                    sum2 = sum2.multiply(new BigInteger(grid[node2.x][i] + ""));
                    System.out.println("x*" + grid[node2.x][i]);
                }
            }
            // 取尾数0个数
            int s1 = getZero(sum.toString());
            System.out.println("sum1="+sum.toString()+" zero num="+s1);
            int s2 = getZero(sum2.toString());
            System.out.println("sum2="+sum2.toString()+" zero num="+s2);
            return Math.max(s1,s2);
        }

        private int getZero(String sumStr) {
            int count = 0;
            int r = sumStr.length();
            while (sumStr.charAt(--r) == '0'){
                count++;
            }
            return count;
        }
    }
    static class Node{
        public int x;
        public int y;
        public int val;

        public Node(int x, int y,int val) {
            this.x = x;
            this.y = y;
            this.val = val;
        }

        @Override
        public String toString() {
            return "Node{" +
                    "x=" + x +
                    ", y=" + y +
                    ", val=" + val +
                    '}';
        }
    }


}
